ArrayList<E>

What Is ArrayList<E>?

ArrayList<E> is a dynamic array implementation of the List interface in Java. It stores elements contiguously in memory and automatically resizes as elements are added. The generic type parameter E specifies the type of elements stored, providing compile-time type safety.

Key Characteristics

• Dynamic sizing: Grows (and can be trimmed) as needed; capacity is managed separately from size.
• Indexed access: Fast random access via get(index) and set(index, value) in O(1) time.
• Insertion/Removal: Appending at the end is amortized O(1). Inserting or removing in the middle requires shifting elements, so it is O(n).
• Order-preserving: Maintains insertion order and allows duplicates and null values.
• Generic: Type parameter E enforces type safety (no casts on retrieval).
• Not synchronized: By default not thread-safe; use wrappers or other collections for concurrency.
• Fail-fast iterators: Iterators detect concurrent structural modification and typically throw ConcurrentModificationException.

Common Operations

// Create with inferred type
ArrayList<String> names = new ArrayList<>();

// Create with initial capacity (reduces resizing if you know the size)
ArrayList<Integer> nums = new ArrayList<>(100);

// Add elements
names.add("Ada");
names.add("Grace");
names.add(1, "Linus"); // insert at index 1

// Access and modify
String first = names.get(0);       // O(1)
names.set(2, "Hopper");            // O(1)

// Remove by index or by value
names.remove(1);                    // O(n) shift
names.remove("Ada");                // O(n) search then shift

// Search
boolean hasGrace = names.contains("Grace"); // O(n)
int idx = names.indexOf("Grace");           // O(n)

// Bulk operations
ArrayList<String> more = new ArrayList<>();
more.add("Edsger");
more.add("Barbara");
names.addAll(more);

// Iteration
for (String s : names) {
    System.out.println(s);
}

// Using an Iterator (supports safe removal during iteration)
Iterator<String> it = names.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.startsWith("B")) {
        it.remove(); // safe structural change
    }
}

// Sorting
names.sort(Comparator.naturalOrder());
// or
Collections.sort(names);

// Convert to array
String[] arr = names.toArray(new String[0]);

// Capacity management
names.ensureCapacity(1000);
names.trimToSize();

Performance Overview

• Access (get/set by index): O(1)
• Append add(e): Amortized O(1); occasional resize is O(n) but infrequent
• Insert/Remove at index: O(n) due to shifting elements
• Search (contains/indexOf): O(n)
• Iteration: O(n)

Internally, capacity grows when needed (commonly by ~1.5x). Pre-sizing with an appropriate initial capacity or using ensureCapacity can reduce reallocations and copying.

When to Use ArrayList<E>

• You need fast random access to elements by index.
• You primarily append to the end rather than insert/remove in the middle.
• You want an order-preserving, resizable array with type safety.

Consider LinkedList<E> when frequent insertions/removals in the middle dominate and indexed access is rare. Prefer arrays when the size is fixed and primitive storage is required (to avoid autoboxing overhead).

Generics and Type Safety

ArrayList<E> uses generics for compile-time type checks. For example, ArrayList<String> rejects non-String elements. Due to type erasure, the runtime representation does not retain E’s type parameter, but compile-time safety prevents class cast errors on retrieval.

Iteration and Fail-Fast Behavior

Iterators over an ArrayList are fail-fast: if the list is structurally modified outside the iterator after its creation, operations like next() may throw ConcurrentModificationException. Use the iterator’s remove() for safe removal during iteration.

Thread Safety

• Not synchronized: Multiple threads modifying the same ArrayList require external synchronization.
• Options include Collections.synchronizedList(new ArrayList<>()) or using CopyOnWriteArrayList for read-heavy, write-light workloads.

Common Pitfalls and Tips

• Middle insertions/removals are O(n); consider data structure choice if this is frequent.
• subList(from, to) returns a view backed by the original list; structural changes to either affect the other. To copy, use new ArrayList<>(list.subList(...)).
• contains and remove(Object) rely on equals; implement it properly for custom types.
• ArrayList holds references; when storing boxed primitives (e.g., Integer), consider boxing overhead.
• Use ensureCapacity when the target size is known to minimize resizes; call trimToSize to reduce memory footprint when growth is complete.

Next Topic